A known navigation device installed in a vehicle performs route guidance from a departure point to a destination point using voice, images, and the like. Such a navigation device is described in, for example, patent document 1. If a vehicle is still traveling after a predetermined time elapses from when the vehicle has reached the vicinity of a destination point and route guidance has ended, the navigation device determines that the vehicle has not reached the destination point and has become lost. Thus, the navigation device restarts the route guidance.